#include <iostream>  
#include <string.h>   
using namespace std;
char m[100];
char c[100];
int gcd(int a, int b)  //辗转相除法求a，b的最大公约数   
{
	int k = 0;
	do
	{
		k = a % b;
		a = b;
		b = k;
	} while (k != 0);
	return a;
}
int Ni(int a, int b)  //求a相对b的逆元   
{
	int i = 0;
	while (a*(++i) % b != 1);  //a*i=1 mod b  
	return i;
}
void Jiami(char m[], int k1, int k2)  //加密   
{
	int len = strlen(m);
	for (int i = 0; i<len; i++)
	{
		c[i] = (k1*(m[i] - 97) + k2) % 26 + 65;    //加密公式 e(x)=k1*x+k2 (mod 26)  
	}
	cout << "加密后的密文为：";
	for (int i = 0; i<len; i++)
		cout << c[i];
	cout << endl;
}
void Jiemi(char c[], int k1, int k2)   //解密   
{
	int len = strlen(c);
	char mm[100];
	for (int i = 0; i<len; i++)
	{
		int t = c[i] - 65 - k2;
		if (t<0) t += 26;
		mm[i] = k1 * t % 26 + 97;    //解密公式 x=k1^-1*(e(x)-k2)(mod26)  
	}
	cout << "解密后的明文为：";
	for (int i = 0; i<len; i++)
		cout << mm[i];
	cout << endl;
}
int main()
{
	char m[100];
	int k1, k2;
	cout << "输入明文：";
	cin >> m;
	cout << "密钥k1和k2：";
	cin >> k1 >> k2;
	while (gcd(k1, 26) != 1)   //判断输入的密钥是否合法   
	{
		cout << "输入的密钥不合法，请重新输入！" << endl;
		cin >> k1 >> k2;
	}
	Jiami(m, k1, k2);
	int k3 = Ni(k1, 26);
	cout << "解密密钥为：";
	cout << k3 << " " << k2 << endl;
	Jiemi(c, k3, k2);
	return 0;
}